{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #最大单词长度乘积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxProduct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大单词长度乘积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串数组&nbsp;<code>words</code>，请计算当两个字符串 <code>words[i]</code> 和 <code>words[j]</code> 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> words = <code>[&quot;abcw&quot;,&quot;baz&quot;,&quot;foo&quot;,&quot;bar&quot;,&quot;fxyz&quot;,&quot;abcdef&quot;]</code>\n",
    "<strong>输出: </strong><code>16 \n",
    "<strong>解释:</strong> 这两个单词为<strong> </strong></code><code>&quot;abcw&quot;, &quot;fxyz&quot;</code>。它们不包含相同字符，且长度的乘积最大。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> words = <code>[&quot;a&quot;,&quot;ab&quot;,&quot;abc&quot;,&quot;d&quot;,&quot;cd&quot;,&quot;bcd&quot;,&quot;abcd&quot;]</code>\n",
    "<strong>输出: </strong><code>4 \n",
    "<strong>解释: </strong></code>这两个单词为 <code>&quot;ab&quot;, &quot;cd&quot;</code>。</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> words = <code>[&quot;a&quot;,&quot;aa&quot;,&quot;aaa&quot;,&quot;aaaa&quot;]</code>\n",
    "<strong>输出: </strong><code>0 \n",
    "<strong>解释: </strong>不存在这样的两个单词。</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= words.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 1000</code></li>\n",
    "\t<li><code>words[i]</code>&nbsp;仅包含小写字母</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 318&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/maximum-product-of-word-lengths/\">https://leetcode-cn.com/problems/maximum-product-of-word-lengths/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [aseY1I](https://leetcode.cn/problems/aseY1I/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [aseY1I](https://leetcode.cn/problems/aseY1I/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        num = [0] * len(words)\n",
    "        A = lambda a, b: a | (1 << (ord(b) - ord('a')))\n",
    "        for i in range (len(words)):\n",
    "            for j in range(len(words[i])):\n",
    "                num[i] = A(num[i],words[i][j])\n",
    "        \n",
    "        \n",
    "        result = 0\n",
    "        for i in range(len(words)-1):\n",
    "            for j in range(i+1,len(words)):\n",
    "                if num[i] & num[j] == 0:\n",
    "                    result = max(result,len(words[i])*len(words[j]))\n",
    "        return result \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        multy = 0\n",
    "        for i in range(len(words)-1):\n",
    "\n",
    "            for j in range(i+1,len(words)):\n",
    "                if not self.commmonchar(i,j,words):\n",
    "                    if len(words[i]) * len(words[j]) > multy:\n",
    "                        multy = len(words[i]) * len(words[j])\n",
    "        return multy\n",
    "\n",
    "    def commmonchar(self,i,j,words):        \n",
    "        for item in words[i]:\n",
    "            if item in words[j]:\n",
    "                return True        \n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "\n",
    "        words = sorted(words, key = lambda x: len(x), reverse=True)\n",
    "        res = 0\n",
    "        n = len(words)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if set(words[i]) & set(words[j]):\n",
    "                    continue\n",
    "                else:\n",
    "                    temp = len(words[i]) * len(words[j])\n",
    "                    res = max(res, temp)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def same(word1, word2):\n",
    "    if len(set(word1) & set(word2)) != 0:\n",
    "        return  False\n",
    "    return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        res = 0\n",
    "        n = len(words)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if same(words[i], words[j]):\n",
    "                    if len(words[i])*len(words[j]) > res:\n",
    "                        res = len(words[i])*len(words[j])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        masks = []\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for s in word:\n",
    "                mask |= (1 << ord(s) - ord('a'))\n",
    "            masks.append(mask)\n",
    "        \n",
    "        ans = 0\n",
    "        for i, wordi in enumerate(words):\n",
    "            for j, wordj in enumerate(words):\n",
    "                f = masks[j] & masks[i]\n",
    "                if not f:\n",
    "                    ans = max(ans, len(wordi) * len(wordj))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        temp = [0]*n\n",
    "        for index,word in enumerate(words):\n",
    "            total = 0\n",
    "            for i in word:\n",
    "                total = (1 << (ord(i)-ord('a'))) | total\n",
    "            temp[index] = total\n",
    "        ans = 0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if temp[i]&temp[j] == 0:\n",
    "                    ans = max(ans,len(words[i])*len(words[j]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        words.sort(key=lambda x:-len(x))\n",
    "        rs = 0\n",
    "        l = len(words)\n",
    "        for i in range(l-1):\n",
    "            for j in range(i+1, l):\n",
    "                tmp_l = len(words[i])*len(words[j])\n",
    "                if tmp_l<=rs:  # 不比之前的大，则略过\n",
    "                    continue\n",
    "                flag = False  # 是否包含相同字符\n",
    "                for ch in words[i]:\n",
    "                    if ch in words[j]:\n",
    "                        flag = True\n",
    "                        break\n",
    "                if not flag:\n",
    "                    rs = tmp_l\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        temp=0\n",
    "        for i in range(len(words)-1):\n",
    "            for j in range(i,len(words)):\n",
    "                if set(words[i]).intersection(words[j])==set() and len(words[i])*len(words[j])>temp:\n",
    "                    temp = len(words[i])*len(words[j])\n",
    "        return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        ans = 0\n",
    "        # words = set(words)\n",
    "        n = len(words)\n",
    "        for i in range(n):\n",
    "            v1 = 0\n",
    "            for ch in words[i]:\n",
    "                v1 |= (1 << (ord(ch) - 97))\n",
    "            for j in range(i+1, n):\n",
    "                v2 = 0\n",
    "                for ch in words[j]:\n",
    "                    v2 |= (1 << (ord(ch) - 97))\n",
    "                if v1 & v2 == 0:\n",
    "                    ans = max(len(words[i]) * len(words[j]), ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        words = sorted(words,key=lambda x:len(x),reverse=True)\n",
    "        ans = 0\n",
    "        for i in range(len(words)-1):\n",
    "            for j in range(i+1,len(words)):\n",
    "                flag = True\n",
    "                for k in words[i]:\n",
    "                    if k in words[j]:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    ans = max(ans,len(words[i])*len(words[j]))\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        masks = [reduce(lambda a, b: a | (1 << (ord(b) - ord('a'))), word, 0) for word in words]\n",
    "        return max((len(x[1]) * len(y[1]) for x, y in product(zip(masks, words), repeat=2) if x[0] & y[0] == 0), default=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        mask = [0] * len(words)\n",
    "        ans = 0\n",
    "        for i in range(len(words)):\n",
    "            for ch in words[i]:\n",
    "                mask[i] |= 1 <<(ord(ch) - ord(\"a\"))\n",
    "\n",
    "            for j in range(0,i):\n",
    "                if mask[j] & mask[i] == 0: # 没有共同字母\n",
    "                    ans = max(ans,len(words[i]) * len(words[j]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        nums = [reduce(or_, (1 << (ord(ch)-97) for ch in word)) for word in words]\n",
    "        ans = 0\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1, len(words)):\n",
    "                if not nums[i] & nums[j]:\n",
    "                    ans = max(ans, len(words[i]) * len(words[j]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1, len(words)):\n",
    "                if not set(words[i]) & set(words[j]):\n",
    "                    ans = max(ans, len(words[i])*len(words[j]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        m = dict()\n",
    "        l = len(words)\n",
    "        for w in words:\n",
    "            n = 0\n",
    "            for t in w:\n",
    "                n |= (1 << ord(t))\n",
    "            if n not in m.keys():\n",
    "                m[n] = len(w)\n",
    "            elif m[n] < len(w):\n",
    "                m[n] = len(w)\n",
    "\n",
    "        return max((m[x] * m[y] for x, y in product(m, repeat=2) if x & y == 0), default=0)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1,n):\n",
    "                t = False\n",
    "                for z in range(97,123):\n",
    "                    if chr(z) in words[i] and chr(z) in words[j]:\n",
    "                        t = True\n",
    "                        break\n",
    "                if not t:\n",
    "                    ans = max(ans,len(words[i]) * len(words[j]))     \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        res=0\n",
    "        m=len(words)\n",
    "        mask=[0]*m\n",
    "        for i in range(m):\n",
    "            for ch in words[i]:\n",
    "                mask[i]|=1<<(ord(ch)-ord(\"a\"))\n",
    "        for i in range(m):\n",
    "            for j in range(i+1, m):\n",
    "                if mask[i]&mask[j]==0:\n",
    "                    res=max(res, len(words[i])*len(words[j]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        marks = [0] * n\n",
    "        for i, x in enumerate(words):\n",
    "            for c in x:\n",
    "                marks[i] |= (1 << (ord(c) - ord('a')))\n",
    "        res = 0\n",
    "        for i in range(n - 1):\n",
    "            for j in range(1, n):\n",
    "                if marks[i] & marks[j] == 0:\n",
    "                    tmp = len(words[i]) * len(words[j]) \n",
    "                    res = max(res, tmp)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "\n",
    "        n = len(words)\n",
    "\n",
    "        max_mul = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                word1 = list(words[i])\n",
    "                word2 = list(words[j])\n",
    "                if len(set(word1) & set(word2)) == 0:\n",
    "                    max_mul = max(len(word1) * len(word2), max_mul)\n",
    "\n",
    "        return max_mul"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        hashset = collections.defaultdict(int)\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            hashset[mask] = max(hashset[mask], len(word))\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        masks = list(hashset.keys())\n",
    "        for i in range(len(masks)):\n",
    "            for j in range(i+1, len(masks)):\n",
    "                if masks[i] & masks[j] == 0:\n",
    "                    ret = max(ret, hashset[masks[i]]*hashset[masks[j]])\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        masks = [reduce(lambda a, b: a | (1 << (ord(b) - ord('a'))), word, 0) for word in words]\n",
    "        return max((len(x[1]) * len(y[1]) for x, y in product(zip(masks, words), repeat=2) if x[0] & y[0] == 0), default=0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        mask = [0 for _ in range(len(words))]\n",
    "        res = 0\n",
    "        for i, word in enumerate(words):\n",
    "            for char in word:\n",
    "                mask[i] |= (1 << (ord(char) - ord('a')))\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1, len(words)):\n",
    "                if mask[i] & mask[j] == 0:\n",
    "                    res = max(res, len(words[i]) * len(words[j]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        # 使用整数来表示每个字符串\n",
    "        word_bits = []\n",
    "        for word in words:\n",
    "            bits = 0\n",
    "            for ch in word:\n",
    "                # 设置字符对应的位\n",
    "                bits |= 1 << (ord(ch) - ord('a'))\n",
    "            word_bits.append(bits)\n",
    "        \n",
    "        max_product = 0\n",
    "        n = len(words)\n",
    "        \n",
    "        # 检查每一对字符串\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if word_bits[i] & word_bits[j] == 0:\n",
    "                    # 更新最大乘积\n",
    "                    max_product = max(max_product, len(words[i]) * len(words[j]))\n",
    "                    \n",
    "        return max_product\n",
    "\n",
    "# 测试\n",
    "sol = Solution()\n",
    "print(sol.maxProduct([\"abc\", \"def\", \"ghi\"]))  # 输出应为 9 (因为 \"abc\" 和 \"def\" 或 \"abc\" 和 \"ghi\" 不包含相同的字符，长度乘积为 3*3=9)\n",
    "print(sol.maxProduct([\"a\", \"aa\", \"aaa\", \"aaaa\"]))  # 输出应为 0（因为没有一对字符串是不包含相同字符的）\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        h = {}\n",
    "        for w in words:\n",
    "            k = sum({1 << (ord(w_) - 97) for w_ in w})\n",
    "            h[k] = max(h.get(k, 0), len(w))\n",
    "\n",
    "        ans = 0\n",
    "        print(h)\n",
    "        for k1 in h:\n",
    "            for k2 in h:\n",
    "                if k1 == k2 or k1 & k2:\n",
    "                    continue\n",
    "                ans = max(h.get(k1) * h.get(k2), ans)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        def encode(s:str) -> int: \n",
    "            code = 0 \n",
    "            for c in s: \n",
    "                code |= 1 << (ord(c)-97)\n",
    "            return code \n",
    "        N, ans = len(words), 0 \n",
    "        words = list(map(lambda w: (len(w), encode(w)), words)) \n",
    "        # print(f\"words: {[bin(words[i][1]) for i in range(N)]}\")\n",
    "        for i in range(1, N): \n",
    "            for j in range(i): \n",
    "                if not words[i][1] & words[j][1]: \n",
    "                    ans = max(ans, words[i][0] * words[j][0])\n",
    "                    # print(f\"{j}, {i}, {ans}\")\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        # masks=[reduce(lambda i,j:i|(1<<(ord(j)-ord('a'))),word,0)for word in words]\n",
    "        #等价于\n",
    "        masks=[]\n",
    "        A = lambda a, b: a | (1 << (ord(b) - ord('a')))#将输入的字母转化为掩码\n",
    "        for i in words:\n",
    "            num = 0 # 掩码默认值为0\n",
    "            for j in i:\n",
    "                num = A(num, j)\n",
    "            masks.append(num) #将转化完的掩码保存至masks数组\n",
    "\n",
    "        # return max((len(x[1]) * len(y[1]) for x, y in  itertools.product(zip(masks, words), repeat=2)  if x[0] & y[0] == 0), default=0)\n",
    "        #等价于\n",
    "        lenmax = 0\n",
    "        for x, y in itertools.product(zip(masks, words), repeat=2): # 对masks, words进行笛卡尔积\n",
    "            if x[0] & y[0] == 0:#xy[0]是掩码 &为0意味着xy没有相同的字母\n",
    "                lenmax = max(len(x[1]) * len(y[1]), lenmax) #对比最大乘积\n",
    "        return lenmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        \n",
    "        sum_total = 0\n",
    "\n",
    "        for i in range(len(words)-1):\n",
    "            sub_nums = set(list(words[i]))\n",
    "            n = len(words[i])\n",
    "\n",
    "            for j in range(i+1, len(words)):\n",
    "                nums = set(list(words[j]))\n",
    "                m = len(words[j])\n",
    "                num = sub_nums.intersection(nums)\n",
    "\n",
    "                if len(num) >0:\n",
    "                    continue\n",
    "                else:\n",
    "                    sum_total = max(m*n, sum_total)\n",
    "                print(sum_total)\n",
    "        \n",
    "        return sum_total\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        maxlength = 0\n",
    "        length = len(words)\n",
    "        i = j =0\n",
    "        for i in range(length):\n",
    "            while(j<i):\n",
    "                print(i)\n",
    "                print(j)\n",
    "                if not (set(words[j]) & set(words[i])):\n",
    "                    maxlength = max(maxlength,len(words[j])*len(words[i]))\n",
    "                j = j+1\n",
    "            j = 0\n",
    "        return maxlength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        m = len(words)\n",
    "        flags = [[False for _ in range(26)] for _ in range(m)]\n",
    "        # 预处理统计每个字符出现的次数\n",
    "        for i in range(m):\n",
    "            for w in words[i]:\n",
    "                flags[i][ord(w) - ord('a')] = True\n",
    "\n",
    "        result = 0\n",
    "        # 通过遍历获取两个值\n",
    "        for i in range(m):\n",
    "            for j in range(i + 1, m):\n",
    "                k = 0\n",
    "                for _ in range(26):\n",
    "                    if flags[i][k] and flags[j][k]:\n",
    "                        break\n",
    "                    k += 1\n",
    "                if k == 26:\n",
    "                    result = max(len(words[i]) * len(words[j]), result)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        def sort_list(li, s, e):\n",
    "            while s >= e:\n",
    "                return\n",
    "            l, h, m = s, e, li[s]\n",
    "            while h > l:\n",
    "                while h>l and len(li[h]) < len(m):\n",
    "                    h-=1\n",
    "                li[l] = li[h]\n",
    "                while h>l and len(li[l]) >= len(m):\n",
    "                    l+=1\n",
    "                li[h] = li[l]\n",
    "            li[l] = m\n",
    "            sort_list(li, s, l-1)\n",
    "            sort_list(li, l+1, e)\n",
    "        n = len(words)\n",
    "        sort_list(words,0, n-1)\n",
    "        ans = [-1, 0]\n",
    "        for i in range(n-1):\n",
    "            xl = len(words[i])\n",
    "            if xl <= ans[0]:\n",
    "                break\n",
    "            for j in range(i+1, n):\n",
    "                yl = len(words[j])\n",
    "                if xl*yl <= ans[1]:\n",
    "                    break\n",
    "                for c in words[i]:\n",
    "                    if c in words[j]:\n",
    "                        break\n",
    "                else:\n",
    "                    ans = [yl, xl*yl]\n",
    "        return ans[1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        flags = [[0] *26  for _ in range(n) ]\n",
    "        res = 0\n",
    "        for  index,word in enumerate(words):\n",
    "            for c in word:\n",
    "                flags[index][ord(c)-ord('a')]=1\n",
    "            \n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                flag = True \n",
    "                for k in range(26):\n",
    "                    if  flags[i][k] and  flags[j][k]:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if  flag:\n",
    "                    res = max(res,len(words[i]*len(words[j])))\n",
    "        return  res \n",
    "        \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        dic = [set(list(word)) for word in words]\n",
    "        res = 0\n",
    "        n = len(words)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if not dic[i].intersection(dic[j]):\n",
    "                    res = max(res,len(words[i])*len(words[j]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n , ans = len(words) , 0\n",
    "        d = [set(list(word)) for word in words]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if not d[i].intersection(d[j]):\n",
    "                    res = len(words[i])*len(words[j])\n",
    "                    ans = max(ans , res)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        dic = [set(word)for word in words]\n",
    "        res = 0\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1, len(words)):\n",
    "                if not dic[i].intersection(dic[j]):\n",
    "                    cur = len(words[i]*len(words[j]))\n",
    "                    res = max(cur, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        dct = [set(list(word)) for word in words]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if not dct[i].intersection(dct[j]):\n",
    "                    cur = len(words[i])*len(words[j])\n",
    "                    if cur > ans:\n",
    "                        ans = cur\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        letters = dict()\n",
    "        lengths = []\n",
    "        for i, w in enumerate(words):\n",
    "            for ch in w:\n",
    "                letters[ch] = letters.get(ch, set())\n",
    "                letters[ch].add(i)\n",
    "            lengths.append(len(w))\n",
    "        \n",
    "        ans = 0\n",
    "        tot = set([i for i in range(len(words))])\n",
    "        for i, w in enumerate(words):\n",
    "            cur = tot \n",
    "            for ch in w:\n",
    "                cur = cur.intersection(tot - letters[ch])\n",
    "                if cur is None:\n",
    "                    break\n",
    "            if cur:\n",
    "                ans = max(ans, lengths[i] * max([lengths[idx] for idx in cur]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        max_length = 0\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1, len(words)):\n",
    "                if len(set(list(words[i])) & set(list(words[j]))) > 0:\n",
    "                    print(len(set(list(words[i])) & set(list(words[j]))))\n",
    "                    continue\n",
    "                \n",
    "                max_length = max(max_length, len(words[i]) * len(words[j]))\n",
    "        \n",
    "        return  max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        # masks = [reduce(lambda a, b: a | (1 << (ord(b) - ord('a'))), word, 0) for word in words]\n",
    "        # return max((len(x[1]) * len(y[1]) for x, y in product(zip(masks, words), repeat=2) if x[0] & y[0] == 0), default=0)\n",
    "        cset = [set(w) for w in words]  # 用集合判断有没有交集\n",
    "# print(cset)[{'c', 'b', 'w', 'a'}, {'b', 'a', 'z'}, {'o', 'f'}, {'b', 'a', 'r'}, {'f', 'x', 'n', 't'}, {'c', 'd', 'f', 'b', 'e', 'a'}]\n",
    "        ans = 0\n",
    "        for i, w in enumerate(words):  # (0,abcw)(1,baz)\n",
    "            for j in range(i + 1, len(words)):\n",
    "                if not cset[i] & cset[j]:  # 若集合没有交集执行以下操作\n",
    "                    ans = max(ans, len(w) * len(words[j]))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        words.sort(key=len,reverse=True)\n",
    "        w = list(map(set,words))\n",
    "        # l = list(map(len,words))\n",
    "        ans = 0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if not (w[i] & w[j]):\n",
    "                    ans = max(ans,len(words[i]) * len(words[j]))\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        from collections import Counter\n",
    "        num = len(words)\n",
    "        counter_list = [Counter(x) for x in words]\n",
    "        max_num = 0\n",
    "        for i in range(num):\n",
    "            for j in range(i+1, num):\n",
    "                flag = False\n",
    "                for k in counter_list[i]:\n",
    "                    if k in counter_list[j]:\n",
    "                        flag = True\n",
    "                if flag is False:\n",
    "                    max_num = max(max_num, len(words[i]*len(words[j])))\n",
    "        return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        from collections import Counter\n",
    "        num = len(words)\n",
    "        counter_list = [Counter(x) for x in words]\n",
    "        max_num = 0\n",
    "        for i in range(num):\n",
    "            for j in range(i+1, num):\n",
    "                if True not in [k in counter_list[j] for k in counter_list[i] ]:\n",
    "                    max_num = max(max_num, len(words[i]*len(words[j])))\n",
    "        return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        cnt = dict()\n",
    "        for w in words:\n",
    "            v = set()\n",
    "            for c in w:\n",
    "                v.add(c)\n",
    "                cnt[w] = v\n",
    "        ans = 0\n",
    "        for w1 in words:\n",
    "            for w2 in words:\n",
    "                if not (cnt[w1] & cnt[w2]):\n",
    "                    ans = max(ans, len(w1) * len(w2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        me = []\n",
    "        for i in range(n):\n",
    "            word = words[i]\n",
    "            temp = {}\n",
    "            for s in word:\n",
    "                temp[s] = 1\n",
    "            me.append(temp)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                dic1 = me[i]\n",
    "                dic2 = me[j]\n",
    "                flag = 0\n",
    "                for k, v in dic1.items():\n",
    "                    if dic2.get(k):\n",
    "                        flag = 1\n",
    "                        break\n",
    "                if flag == 0:\n",
    "                    ans = max(ans, len(words[i]) * len(words[j]))\n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        def sort_list(li, s, e):\n",
    "            while s >= e:\n",
    "                return\n",
    "            l, h, m = s, e, li[s]\n",
    "            while h > l:\n",
    "                while h>l and len(li[h]) < len(m):\n",
    "                    h-=1\n",
    "                li[l] = li[h]\n",
    "                while h>l and len(li[l]) >= len(m):\n",
    "                    l+=1\n",
    "                li[h] = li[l]\n",
    "            li[l] = m\n",
    "            sort_list(li, s, l-1)\n",
    "            sort_list(li, l+1, e)\n",
    "        n = len(words)\n",
    "        sort_list(words,0, n-1)\n",
    "        print(words)\n",
    "        ans = [-1, 0]\n",
    "        for i in range(n-1):\n",
    "            xl = len(words[i])\n",
    "            if xl <= ans[0]:\n",
    "                break\n",
    "            for j in range(i+1, n):\n",
    "                yl = len(words[j])\n",
    "                if xl*yl <= ans[1]:\n",
    "                    break\n",
    "                for c in words[i]:\n",
    "                    if c in words[j]:\n",
    "                        break\n",
    "                else:\n",
    "                    ans = [yl, xl*yl]\n",
    "        print(ans)\n",
    "        return ans[1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        s = list()\n",
    "        for i in range(len(words)):\n",
    "            s.append(set(list(words[i])))\n",
    "        ans = 0\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i + 1, len(words)):\n",
    "                if not s[i] & s[j]:\n",
    "                    ans = max(ans, len(words[i] * len(words[j])))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words) -> int:\n",
    "        maxlen=0\n",
    "        breaks=1\n",
    "        dis = [{} for i in range(len(words))]\n",
    "        for i in range(len(words)):\n",
    "            for k in range(len(words[i])):\n",
    "                if not dis[i].get(words[i][k]):\n",
    "                    dis[i][words[i][k]]=1\n",
    "\n",
    "        for i in range(len(words)-1):\n",
    "            for j in range(i+1,len(words)):\n",
    "                if len(words[i])*len(words[j])<maxlen:\n",
    "                    continue\n",
    "                for k in range(len(dis[i])):\n",
    "                    if dis[j].get(list(dis[i].keys())[k]):\n",
    "                        breaks=0\n",
    "                        break\n",
    "                if breaks==1:\n",
    "                    maxlen=len(words[i])*len(words[j])\n",
    "                breaks=1\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        ans = 0\n",
    "        wordsLen = [len(word) for word in words]\n",
    "        words = [set(word) for word in words]\n",
    "        for i in range(len(words) - 1):\n",
    "            for j in range(i, len(words)):\n",
    "                if not words[i] & words[j]:\n",
    "                    ans = max(ans, wordsLen[i] * wordsLen[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        ans = 0\n",
    "        l = len(words)\n",
    "        temp = []\n",
    "        for i in range(l):temp.append(set(words[i]))\n",
    "        print(temp)\n",
    "        for i in range(l-1):\n",
    "            for j in range(i, l):\n",
    "                if not (temp[i] & temp[j]):\n",
    "                    ans = max(ans, len(words[i])*len(words[j]))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        lst = []\n",
    "        max_res = 0\n",
    "        for word in words:\n",
    "            lst.append([len(word), set(word)])\n",
    "        for i in range(len(lst)):\n",
    "            l1, w1 = lst[i]\n",
    "            for l2, w2 in lst[i+1:]:\n",
    "                if len(w1 & w2) == 0:\n",
    "                    res = l1 * l2\n",
    "                    max_res = res if res > max_res else max_res\n",
    "        return max_res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        maxPair = 0\n",
    "        original = words[:]\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i + 1, len(words)):\n",
    "                if type(words[i]) == str:\n",
    "                    words[i] = set(words[i])\n",
    "                if type(words[j]) == str:\n",
    "                    words[j] = set(words[j])\n",
    "                inter = words[i] ^ words[j]\n",
    "                if len(words[i]) + len(words[j]) == len(inter):\n",
    "                    a = len(original[i]) * len(original[j])\n",
    "                    if a > maxPair:\n",
    "                        maxPair = a\n",
    "        return maxPair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words) -> int:\n",
    "        dic1={}\n",
    "        for k in words:\n",
    "            dic1[k]=len(k)\n",
    "        dic1=dict(sorted(dic1.items(),key=lambda x:x[1],reverse=True))\n",
    "        dic2={}\n",
    "        lis=list(dic1.keys())\n",
    "        for i in dic1:\n",
    "            now={}\n",
    "            for t in i:\n",
    "                now[t]=1\n",
    "            dic2[i]=now\n",
    "        max=0\n",
    "        for i in range(len(lis)):\n",
    "            for j in range(i+1,len(lis)):\n",
    "                if len(lis[i])*len(lis[j])<max:\n",
    "                    break\n",
    "                if self.ifsame(dic2[lis[i]],dic2[lis[j]]):\n",
    "                    max=len(lis[i])*len(lis[j])\n",
    "        return max\n",
    "\n",
    "    def ifsame(self,dic1,dic2):\n",
    "        for i in dic1:\n",
    "            if i in dic2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        info = []\n",
    "        for word in words:\n",
    "            info.append(Counter(word))\n",
    "        res = 0\n",
    "        for i,e in enumerate(info):\n",
    "            for j in info[i+1:]:\n",
    "                for k in range(26):\n",
    "                    if e[chr(ord(\"a\")+k)] and j[chr(ord(\"a\")+k)]:\n",
    "                        break\n",
    "                if k==25:\n",
    "                    res = max(res,len(words[i])*sum(j.values()))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words) -> int:\n",
    "        dic1={}\n",
    "        for k in words:\n",
    "            dic1[k]=len(k)\n",
    "        dic1=dict(sorted(dic1.items(),key=lambda x:x[1],reverse=True))\n",
    "        dic2={}\n",
    "        lis=list(dic1.keys())\n",
    "        for i in dic1:\n",
    "            now={}\n",
    "            for t in i:\n",
    "                now[t]=1\n",
    "            dic2[i]=dict(sorted(now.items(),key=lambda x:x[0],reverse=True))\n",
    "        max=0\n",
    "        for i in range(len(lis)):\n",
    "            for j in range(i+1,len(lis)):\n",
    "                if len(lis[i])*len(lis[j])<max:\n",
    "                    break\n",
    "                if self.ifsame(dic2[lis[i]],dic2[lis[j]]):\n",
    "                    max=len(lis[i])*len(lis[j])\n",
    "        return max\n",
    "\n",
    "    def ifsame(self,dic1,dic2):\n",
    "        for i in dic1:\n",
    "            if i in dic2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        ret = 0\n",
    "        masks = []\n",
    "\n",
    "        for v in words:\n",
    "            masks.append(set(v))\n",
    "\n",
    "        for i, v1 in enumerate(masks):\n",
    "            for j, v2 in enumerate(masks[i+1:]):\n",
    "                ilen1 = len(v1 | v2)\n",
    "                ilen2 = len(v1) + len(v2)\n",
    "                if ilen1 == ilen2:\n",
    "                    ret = max(ret, len(words[i])*len(words[j+i+1]))\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        new_words = []\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i,len(words)):\n",
    "                if_in = False\n",
    "                for letter in words[i]:\n",
    "                    if letter in words[j]:\n",
    "                        if_in = True\n",
    "                        break\n",
    "                if not if_in:\n",
    "                    #两个单词没有相同字母\n",
    "                    new_words.append(len(words[i]))\n",
    "                    new_words.append(len(words[j]))\n",
    "        max = 0\n",
    "        for i in range(len(new_words)//2):\n",
    "            n = new_words[i*2]*new_words[i*2+1]\n",
    "            if n>max:\n",
    "                max = n\n",
    "\n",
    "        return max\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        ws = [set(i) for i in words]\n",
    "    \n",
    "        ans = 0\n",
    "        for i in range(len(ws)):\n",
    "            for j in range(i+1, len(ws)):\n",
    "                if ws[i] & ws[j] == set():\n",
    "                    ans = max(ans, len(words[i])*len(words[j]))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        ws = [set(i) for i in words]\n",
    "    \n",
    "        ans = 0\n",
    "        for i in range(len(ws)):\n",
    "            for j in range(i+1, len(ws)):\n",
    "                if ws[i] & ws[j] == set():\n",
    "                    ans = max(ans, len(words[i])*len(words[j]))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        word_set = [set(x) for x in words]\n",
    "        res = 0\n",
    "        for i, x in enumerate(word_set):\n",
    "            for j in range(i+1, len(words)):\n",
    "                y = word_set[j]\n",
    "                if x - y == x and y - x == y:\n",
    "                    res = max(res, len(words[i])*len(words[j]))\n",
    "        \n",
    "        return res\n",
    "        return max([len(x) * len(y) for x in words for y in words if set(x)-set(y)== set(x) and set(y)-set(x)==set(y)], default=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        w = [set(w) for w in words]\n",
    "        res = 0\n",
    "        for i in range(0, len(words)):\n",
    "            for j in range(i, len(words)):\n",
    "                if not w[i].intersection(w[j]):\n",
    "                    res = max(len(words[i]) * len(words[j]), res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        words_new = [set(one) for one in words]\n",
    "        res = 0\n",
    "        for i in range(len(words_new)):\n",
    "            for j in range(i+1,len(words_new)):\n",
    "                if not words_new[i].intersection(words_new[j]):\n",
    "                    res = max(res,len(words[i])* len(words[j]))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        res1 = [set(one) for one in words]\n",
    "        maxr = -inf\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1,len(words)):\n",
    "                s1 = res1[i]\n",
    "                s2 = res1[j]\n",
    "                if not s1.intersection(s2):\n",
    "                    maxr = max(maxr,len(words[i]) * len(words[j]))\n",
    "        if maxr == -inf:\n",
    "            return 0\n",
    "        return maxr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        dct = [set(list(word)) for word in words]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if not dct[i].intersection(dct[j]):\n",
    "                    cur = len(words[i]) * len(words[j])\n",
    "                    if cur > ans:\n",
    "                        ans = cur\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        ws = [set(i) for i in words]\n",
    "    \n",
    "        ans = 0\n",
    "        for i in range(len(ws)):\n",
    "            for j in range(i+1, len(ws)):\n",
    "                if ws[i] & ws[j] == set():\n",
    "                    ans = max(ans, len(words[i])*len(words[j]))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        res1 = [set(one) for one in words]\n",
    "        maxr = 0\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1,len(words)):\n",
    "                s1 = res1[i]\n",
    "                s2 = res1[j]\n",
    "                if not s1.intersection(s2):\n",
    "                    maxr = max(maxr,len(words[i]) * len(words[j]))\n",
    "        return maxr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        # 没用位运算，以后再看吧，手动狗头\n",
    "        # intersection()方法返回两个或更多集合中都包含的元素，即交集\n",
    "        lst = [set(s) for s in words]\n",
    "        res = 0\n",
    "        for i in range(len(lst)):\n",
    "            for j in range(i+1, len(lst)):\n",
    "                if not lst[i].intersection(lst[j]):\n",
    "                    res = max(res, len(words[i]) * len(words[j]))\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
